/*
 * =====================================================================================
 *
 *       Filename:  8-13.cpp
 *
 *    Description:  编程珠玑 第八章 问题13
 *
 *        Version:  1.0
 *        Created:  2011-11-16 14:02:55
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include <iostream>
#include <iterator>
#include "UserTime.h"

int max_sum_seque(int *array, int rows, int cols)
{
    int *A = new int[(rows + 1) * (cols + 1)];

    for (int i = 0; i <= rows; ++i) {
        A[i * (rows + 1) + 0] = 0;
    }
    for (int j = 0; j <= cols; ++j) {
        A[(0) * (rows + 1) + j] = 0;
    }

    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            A[i * (rows + 1) + j] = array[(i - 1) * rows + (j - 1)]
                                    + A[(i - 1) * (rows + 1) + j]
                                    + A[i * (rows + 1) + j - 1]
                                    - A[(i - 1) * (rows + 1) + j - 1];
        }
    }

    int maxsofar = 0;
    for (int mini = 1; mini <= rows; ++mini)
        for (int maxi = mini; maxi <= rows; ++maxi)
            for (int minj = 1; minj <= cols; ++minj)
                for (int maxj = minj; maxj <= cols; ++maxj) {
                    int tmp = A[maxi * (rows + 1) + maxj]
                              - A[maxi * (rows + 1) + (minj - 1)]
                              - A[(mini - 1) * (rows + 1) + maxj]
                              + A[(mini - 1) * (rows + 1) + (minj - 1)];
                    maxsofar = (std::max)(maxsofar, tmp);
                }

    delete [] A;

    return maxsofar;
}

int sum_col(int *array, int rows, int cols, int arow, int brow, int icol)
{
    int sum = 0;
    for (int i = arow; i <= brow; ++i) {
        sum += array[i * rows + icol];
    }
    return sum;
}

int max_sum_seque2(int *array, int rows, int cols)
{
    int max_matrix = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int maxsofar = 0;
            int maxendsofar = 0;
            for (int k = 0; k < cols; ++k) {
                maxendsofar = (std::max)(maxendsofar + sum_col(array, rows, cols, i, j, k), 0);
                maxsofar = (std::max)(maxsofar, maxendsofar);
            }
            max_matrix = (std::max)(max_matrix, maxsofar);
        }
    }

    return max_matrix;
}

int main(int argc, char *argv[])
{
    const int cnt = 20;
    int *array = new int[cnt * cnt];
    for (int i = 0; i < cnt; ++i) {
        for (int j = 0; j < cnt; ++j) {
            array[i * cnt + j] = range_rand(-cnt, cnt);
        }
    }

    for (int row = 0; row < cnt; ++row) {
        std::copy(&array[row * cnt + 0], &array[row * cnt + cnt], std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    }
    std::cout << "max_sum_seque : the max is " << max_sum_seque(array, cnt, cnt) << std::endl;
    std::cout << "max_sum_seque2 : the max is " << max_sum_seque2(array, cnt, cnt) << std::endl;


    int A[3][3] = {
        { -1, 2, 3},
        { -2, -1, 2},
        { -4, 1, 2}
    };
    for (int row = 0; row < 3; ++row) {
        std::copy(&A[row][0], &A[row][3], std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    }
    std::cout << "max_sum_seque : the max is " << max_sum_seque(&A[0][0], 3, 3) << std::endl;
    std::cout << "max_sum_seque2 : the max is " << max_sum_seque2(&A[0][0], 3, 3) << std::endl;

    delete [] array;
    return 0;
}
